#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ans = 0;
        int len = nums.size();

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int z = j + 1; z < len; z++) {
                    if (nums[i] + nums[j] <= nums[z])continue;
                    if (nums[j] + nums[z] <= nums[i])continue;
                    if (nums[z] + nums[i] <= nums[j])continue;
                    ans++;
                }
            }
        }
        return ans;
    }
};


class Solution2 {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int len = nums.size();

        for (int k = len - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    //cout<<ans<<" "<<i<<" "<< j<<  " "<< k<< endl;
                    ans += j - i;
                    j -= 1;

                }
                else i++;
            }

        }
        return ans;
    }
};